The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


Target-heavy Feistel Networks. These are the opposite: Feistel-type networks where the F-function has a larger output than input. Tiger [AB96b] uses a 64-by-192-bit target-heavy structure. Figure 7.5 shows a target-heavy 2-round Feistel network.

Other Variants. There are other round function structures, which are variants of the above. IDEA [LMM91] is a variant of an SP-network, for example. In “fenced” constructions, multiple parallel implementations of the same structure are separated by specially constructed mixing operations [Rit96].


Fig. 7.4.  A Source-heavy 2-round Feistel Network


Fig. 7.5.  A Target-heavy 2-round Feistel Network

Although there has been some analysis of incomplete, source-heavy, and target-heavy Feistel networks [SK96], they are not nearly as well-understood as Feistel and SP networks. Given the current state of analysis, we discarded any of the newer structures.

Our Choice. Twofish was designed as a Feistel network, primarily because it is one of the most studied block-cipher building blocks, but also because the Feistel structure takes care of its own inverse. The structure of a Feistel network means that the F function need only be calculated in one direction.4 This means that we were able to use operations in our F function that are inefficient in the other direction, and make do with tables and constants for one direction only. Contrast this with an SP-network, which must execute its encryption function in both the forward and backward directions.


4In fact, the F function can be non-surjective, as it is in DES or Blowfish.

7.2 The Key-dependent S-boxes

A fundamental component of Twofish is the set of four key-dependent S-boxes. These must have several properties:

  The four different S-boxes actually need to be different.
  Few or no keys may cause the S-boxes used to be “weak,” in the sense of having high-probability differential or linear characteristics, or in the sense of having a very simple algebraic representation.
  There should be few or no pairs of keys that define the same S-boxes. That is, changing even one bit of the key used to define an S-box should always lead to a different S-box. In fact, these pairs of keys should lead to extremely different S-boxes.

7.2.1 The Fixed Permutations q0 and q1

The construction method for building q0 and q1 from 4-bit permutations (specified in Section 4.3.5) was chosen because it decreases hardware and memory costs for some implementations, as discussed previously, without adding any apparent weaknesses to the cipher. It is helpful to recall that these individual fixed-byte permutations are used only to construct the key-dependent S-boxes, which, in turn, are used only within the h and g functions. In particular, the individual characteristics of q0 and q1 are not terribly relevant (except perhaps in some related-key attacks), because Twofish always uses at least three of these permutations in series together with at least two XORs with key material bytes.

Consideration was initially given to using random full 8-bit permutations for q0 and q1, as well as algebraically derived permutations (e.g., multiplicative inverses over GF(28)) that have slightly better individual permutation characteristics, but no substantial improvement was found when composite keyed S-boxes were constructed and compared to the q0 and q1 used in Two-fish.

The construction of q0 and q1 is a basically a 2-round SP network. We investigated several possible constructions. The main alternative was a 3- or 4-round Feistel network. We chose the SP network, as it has a lower circuit-depth. This reduces the propagation delay in a hardware implementation of the q-box. As several q-boxes are used in series, an increase in propagation delay has significant effects on the hardware speed of the cipher.

The q0 and q1 permutations were constructed by performing a random search for the 4-bit permutations t0, t1, t2, and t3. Using the notation of Matsui [Mat96], we define

and

where q is the mapping DPmax and LPmax are being computed for, the probabilities are taken over a uniformly distributed X, and the operator computes the overall parity of the bitwise-AND of its two operands. Only fixed permutations with DPmax ≤ 10/256, LPmax ≤ 1/16, and fewer than three fixed points5 were accepted as potential candidates. These criteria alone rejected over 99.8 percent of all randomly chosen permutations of the given construction. Pairs of permutations meeting these criteria were then evaluated as potential (q0, q1) pairs, computing various metrics when combined with key material into Twofish’s S-box structure, as described below.


5A fixed point for a function f is a value x such that f(x) = x.

The actual q0 and q1 chosen were one of several pairs with virtually identical statistics that were found with only a few tens of hours of searching on Pentium class computers. Each permutation has DPmax = 10/256 and LPmax = 1/16; q0 has one fixed point, while q1 has two fixed points.

7.2.2 The S-boxes.

Each S-box is defined with two, three, or four bytes of key material, depending on the Twofish key size. This is done as follows for 128-bit Twofish keys:

s0(x) = q1[q0[q0[x] ⊕ s0,0] ⊕ s1,0]
s1(x) = q0[q0[q1[x] ⊕ s0,1] ⊕ s1,1]
s2(x) = q1[q1[q0[x] ⊕ s0,2] ⊕ s1,2]
s3(x) = q0[q1[q1[x] ⊕ s0,3] ⊕ s1,3]

where the si,j are the bytes derived from the key bytes using the RS matrix. Note that if s0,i = s0,j and s1,i = s1,j for ij, then si(x) ≠ sj(x) for most values of x. In fact, as each S-box uses a unique order of q-boxes, it is extremely unlikely that two different S-boxes could produce the identical mapping.

Note that when all si,j = 0, then s0(x) = q1[s1(q1–1[x])]. Similar relationships hold between other S-boxes. We have not been able to find any weaknesses resulting from this, as long as q0 and q1 have no high-probability differential characteristics.

In some sense this construction is similar to a rotor machine [PB92, DK85, Bau93, Bau97], with two different types of rotor (q0 and q1). The first rotor is fixed, and the fixed offset between two rotors is specified by a key byte. We did not find any useful cryptanalysis from this parallel, but someone else might.

For the 128-bit key, we have experimentally verified that each N/8-bit key used to define a byte permutation results in a distinct permutation. For example, in the case of a 128-bit key, the S-box s0 uses 16 bits of key material. Each of the 216 s0 permutations defined is distinct, as is also the case for s1, s2, and s3. We have not yet exhaustively tested longer key lengths, but we conjecture that all S-boxes generated by our construction are distinct. We also conjecture that this would be the case for almost all choices of q0 and q1 meeting the basic criteria discussed above.


Previous Table of Contents Next